'''
Created on Feb 27, 2011

@author: Roni
'''
from cliques.cliqueAlgorithm import cliqueAlgorithm
import logging 
import random
from cliques.radixTree import RadixTree

class RLS(cliqueAlgorithm):
    ''' 
    Implementation of the reactive local search algorithm (RLS-LTM) with the long term memory addition. 
    Bibliography:
    [1] Reactive and dynamic local search for max-clique: Engineering effective building blocks, 
        Roberto Battiti and Franco Mascia, Computers and Operational Research 2009.
    [2] Reactive Local Search for the Maximum Clique Problem, Roberto Battiti and Marco Protasi, Algorithmica 2001 
    '''
    ADD_MOVE = 'Add'              # Add move type
    DELETE_MOVE = 'Delete'        # Delete move type
    
    def __init__(self,tie_breaking="Random"):
        '''
        Constructor
        '''
        cliqueAlgorithm.__init__(self)
        self.random = random.Random()
        self.tie_breaking = tie_breaking
        
       

    def __str__(self):
        if self.tie_breaking!="Random":
            return "RLS-LTM-%s" % self.tie_breaking
        else:
            return "RLS-LTM"

    def setup(self, unknown_graph, k, start_node):
        '''
        Setup the relevant data structures
        '''
        self.current_clique = []
        self.prohibition_time = 1
        self.last_stale_iteration = 0 # Last iteration where no new clique was checked
        self.largest_clique_iteration = 0 # The last iteration where the largest clique so far has been seen
        self.max_clique_size_found = 0 # The size of the largest clique found so far
        self.restart_constant = 100 # Number of stale iterations until a restart occurs
        self.last_cycle = 0 # The last iteration where a cycle has been spotted and restart did not occur
        self.largest_clique_so_far = 0 # The size of the largest clique found so far
        self.largest_clique = None # The largest clique found so far
        self.cliques_container = RadixTree()
        self.last_move = dict() # States for every node the last iteration were that node was added or deleted from the current clique
        self.missing = dict() # Counts for every node in the graph the number of edges missing to make it a possible addition to the current clique
        self.missing_list = dict() # Lists for every node in the graph the nodes that are not neighbors of that node and are part of the current clique 
        self.delta_possible_add = dict() # Counts for every node the number of nodes that will be added to "possible adds" if that node will be removed from the current clique
        self.possible_adds = [] # List of nodes that can be added to the current clique (i.e., their are their common neighbors)
        
        cliqueAlgorithm.setup(self, unknown_graph, k, start_node)
        
        self.missing_list[start_node]=[]
        self.missing[start_node]=0                
        self.delta_possible_add[start_node]=0        
        
    def __find_not_neighbors(self,node):
        ''' Returns a list of all the nodes that are not neighbors of node '''
        neighbors = self.ckg.neighbors(node)
        return [a_node for a_node in self.ckg.nodes() if a_node not in neighbors and a_node!=node]
        
        
    def __update(self,current_node, move_type):
        '''
        Update possible adds after adding 
        '''
        logging.debug("Updating after %s of node %s" % (move_type, current_node))
        self.last_move[current_node]=self.iteration
        neighbors = self.ckg.neighbors(current_node)
        not_neighbors = self.__find_not_neighbors(current_node)

        # Special initialization for first iteration
        if self.iteration==0:
            self.possible_adds = list(neighbors)            
            self.one_missing = dict()
            for node in not_neighbors:
                self.one_missing[node]=current_node
                self.missing_list[node]=[current_node]
            return

 
        # Handle ADD move
        if move_type==RLS.ADD_MOVE:
            self.possible_adds.remove(current_node)
            
            current_delta_possible_add=0
            for node in not_neighbors:
                old_missing = self.missing[node]
                                
                self.missing[node] = old_missing+1
                self.missing_list[node].append(current_node)
                
                # If node was a potential addition to the current clique - now it is not
                if old_missing==0:
                    # A node with old missing = 0 can not be in possible adds if it was removed from the current clique
                    if node in self.possible_adds:
                        self.possible_adds.remove(node)
                    self.one_missing[node]=current_node
                    current_delta_possible_add=current_delta_possible_add+1
                    
                # If node was previously almost a potential addition to the current clique - now it is not
                elif old_missing==1: #
                    old_missing_node = self.one_missing[node]
                    self.one_missing.pop(node)
                    self.delta_possible_add[old_missing_node]=self.delta_possible_add[old_missing_node]-1
            
            # Set the number of nodes that will be added to possible adds if current node is removed
            self.delta_possible_add[current_node]=current_delta_possible_add
            
        # Handle DELETE move
        elif move_type==RLS.DELETE_MOVE:
            # Since current node is not in the current clique anymore - 
            # no point in its delta possible add list
            self.delta_possible_add[current_node]=-1                         
            for node in not_neighbors:
                old_missing = self.missing[node]                
                self.missing[node]=old_missing-1
                self.missing_list[node].remove(current_node)
                
                # If now this node can be added to the current clique - add it to possible adds list
                if old_missing==1:
                    self.one_missing.pop(node)
                    self.possible_adds.append(node)                  
                elif old_missing==2:
                    missing_node = self.missing_list[node][0] # Old missing was 2, one was removed, only one left
                    self.one_missing[node]=missing_node
                    self.delta_possible_add[missing_node]=self.delta_possible_add[missing_node]+1                    
        else:
            raise ValueError("Illegal move type %s" % move_type)

    def step(self):
        ''' Overridden from base class. 
        Performs a single step of the algorithm.
        ''' 
        if(self.iteration==0):        
            self.current_clique = [self.start_node]
            self.expand(self.start_node)
            self.__update(self.start_node, RLS.ADD_MOVE)
        else:
            self.prohibition_time = self.memory_reaction()
            self.current_clique = self.best_neighbor()
        
        current_clique_size = len(self.current_clique)
        if self.largest_clique_so_far<current_clique_size:
            self.largest_clique_so_far = current_clique_size
            self.largest_clique=self.current_clique
        
        self.iteration=self.iteration+1
        
        logging.debug("%d: T=%d, Clique %s Expanded %s PA %s" % \
                     (self.iteration, self.prohibition_time,self.current_clique,self.expanded,self.possible_adds))
        
        # Check if current clique is the new largest clique
        if current_clique_size>self.max_clique_size_found:
            self.max_clique_size_found=current_clique_size
            self.largest_clique_iteration = self.iteration
            logging.debug("Largest clique updated to %d" %self.max_clique_size_found)
    

        # Check if need ot do random restart (this occurs when the search goes stale)            
        if self.iteration-self.last_stale_iteration> self.restart_constant:
            logging.debug("Restart (iteration %d)" % self.iteration)
            self.last_stale_iteration=self.iteration
            self.restart()
    
    def restart(self):
        ''' Restart the clique search, starting from a new (known) node '''
        if len(self.generated)>0:
            degrees = [self.ckg.order(node) for node in self.generated]
            max_degree = max(degrees)
            candidates = [node for node in self.generated if self.ckg.order(node)==max_degree]
            selection = self.random.choice(candidates)
            self.possible_adds = list(self.ckg.nodes())
            self.one_missing = dict()
            for node in self.ckg.nodes():
                self.missing_list[node]=[]
                self.missing[node]=0                
                self.delta_possible_add[node]=0
            self.current_clique = [selection]
            self.__update(selection, RLS.ADD_MOVE)
        else:
            logging.debug("No generated left. This means that no clique can be found")
            
    
    
    def memory_reaction(self):
        ''' Calculate the prohibition time according to how stale was the current step '''
        self.iteration=self.iteration+1        
        duplicate = self.cliques_container.find(self.current_clique)

        if duplicate is not None:           
            cycle_length = self.iteration-duplicate.value
            duplicate.value = self.iteration
            if cycle_length< 2*(self.k-1):
                self.last_cycle = self.iteration
                return self.increase_prohibition_time()
        else:
            self.cliques_container.insert(self.current_clique,self.iteration)
        
        if self.iteration-self.last_cycle>10*self.max_clique_size_found:
            self.last_cycle=self.iteration
            return self.decrease_prohibition_time()
        return self.prohibition_time
    
    def increase_prohibition_time(self):
        return min(max(1.1*self.prohibition_time,self.prohibition_time+1),self.k*0.5)
    def decrease_prohibition_time(self):
        return max(min(0.9*self.prohibition_time,self.prohibition_time-1),1)
    
    def __is_allowed(self,node):
        ''' Returns true if the given node is allowed in the current iteration '''
        iteration_of_last_move = self.last_move.setdefault(node,-1)
        if iteration_of_last_move==-1:
            return True
        else:
            return self.prohibition_time<self.iteration-iteration_of_last_move
    
    def best_neighbor(self):
        '''
        Return the new current clique: make a add move, or a replace move.        
        '''     
        selection = None 
        move_type = None
        if len(self.possible_adds)>0:
            candidates = [node for node in self.possible_adds if self.__is_allowed(node)]

            num_of_candidates = len(candidates)
            if num_of_candidates>0:
                # If tie break towards candidates with highest degree - prune candidates with lesser degree
                if self.tie_breaking=="Degree":
                    max_degree_candidates = []
                    max_degree = -1
                    for node in candidates:
                        degree = self.ckg.order(node)
                        if degree>max_degree:
                            max_degree = degree
                            del max_degree_candidates[:]
                            max_degree_candidates.append(node)
                        elif degree==max_degree:
                            max_degree_candidates.append(node)
                    candidates = max_degree_candidates
                    
                selection = self.random.choice(candidates)

                move_type = RLS.ADD_MOVE
        
        # If no node can be added - try a drop move
        if selection is None:
            # TODO: Make only one loop for efficiency
            candidates = [node for node in self.current_clique if self.__is_allowed(node)]
            if len(candidates)>0:
                max_delta = max([self.delta_possible_add[node] for node in candidates])
                candidates = [node for node in candidates if self.delta_possible_add[node]==max_delta]
                selection = self.random.choice(candidates)
            else:
                # TODO: Understand how this is possible
                if len(self.current_clique)==0:
                    return self.current_clique
                selection = self.random.choice(self.current_clique)
            move_type = RLS.DELETE_MOVE
        
        # Explores a node if it has not been explored yet
        if selection not in self.expanded:
            logging.debug("Expanding %s ..." % selection)
            self.expand(selection) 
        
        self.__update(selection, move_type)
        if move_type==RLS.ADD_MOVE:
            self.current_clique = self.extend(self.current_clique,selection)
        elif move_type==RLS.DELETE_MOVE:
            self.current_clique = self.remove(self.current_clique,selection) 
        else:
            raise ValueError("Illegal move type %s" % move_type)
        return self.current_clique

 
    def generate(self,parent,new_node):
        ''' 
        Override node generation to also update RLS variables:
        possible_adds, one_missing, missing_list and missing 
         '''
        cliqueAlgorithm.generate(self,parent, new_node)
        
        # If new node is already in possible adds - no changes are needed
        if new_node in self.possible_adds:
            return

        # If this is the first time that this node is generated - update missing and missing_list
        if len(self.ckg.neighbors(new_node))==1:
            new_missing_list = []
            for clique_node in self.current_clique:
                if clique_node!=parent:
                    new_missing_list.append(clique_node)
            self.missing[new_node]=len(new_missing_list)
            self.missing_list[new_node]=new_missing_list
            
            if len(new_missing_list)==0:
                self.possible_adds.append(new_node)
            elif len(new_missing_list)==1:
                missing_neighbor = new_missing_list[0]
                self.one_missing[new_node]=missing_neighbor
                self.delta_possible_add[missing_neighbor]=self.delta_possible_add[missing_neighbor]+1
                
        # Otherwise, this is not the first time that this node is generated, only a new edge was introduced (parent-new_node)            
        else:
            new_missing_list = self.missing_list[new_node]
            if parent in new_missing_list:
                new_missing_list.remove(parent)
                missing_list_size = len(new_missing_list)
                self.missing[new_node]=missing_list_size
                
                # If new_node should now be added to possible_adds 
                if missing_list_size==0:
                    self.one_missing.pop(new_node)
                    self.possible_adds.append(new_node)
                    self.delta_possible_add[parent]=self.delta_possible_add[parent]-1
                # If new_node should be added to one_missing
                elif missing_list_size==1: 
                    missing_neighbor = new_missing_list[0]
                    self.one_missing[new_node]=missing_neighbor
                    self.delta_possible_add[missing_neighbor]=self.delta_possible_add[missing_neighbor]+1
        
    def halt(self):
        return self.max_clique_size_found>=self.k or len(self.generated)==0
    
    def clique_found(self):
        self.done = self.max_clique_size_found>=self.k
        return self.done
        
    def choose_node(self):
        raise ValueError("choose_node() not implemented in RLS")
        
    def output_clique(self):
        return self.largest_clique
        
    def extend(self,clique, node):
        '''
        Create a new list of nodes with all the nodes in clique and the new node (node).
        Maintain order of nodes.
        '''
        new_nodes= list()
        node_added = False
        for clique_member in clique:
            if node<clique_member and node_added==False:
                node_added=True
                new_nodes.append(node)
                new_nodes.append(clique_member)
            else:
                new_nodes.append(clique_member)
        if node_added==False:
            new_nodes.append(node)

        return new_nodes
    
    def remove(self,clique, node):        
        new_nodes = list(clique)
        new_nodes.remove(node)
        return new_nodes
        

        
        

